#include<iostream>
using namespace std;

//剑指offer题1：在一个二维数组中，每一行都按照从左往右递增的顺序排序，每一列都按照从上往下递增的顺序排序。
//完成一个函数，输入一个数，判断该数是否在数组中。（ps:可以从四个角开始查起，其中从左下角和右上角查起思路比较清晰）
//      思路一：从左下角来看，向上数字递减，向右数字递增，
//            因此，从左下角开始，当要查的数字比左下角数字大时，右移；否则上移
#include<vector>
bool Find(vector<vector<int> > arr, int target)
{
	int rowcount = arr.size();
	int colcount = arr[0].size();
	
	int i, j;
	for (i = rowcount - 1, j = 0; i >= 0 && j < colcount;)
	{
		if (target == arr[i][j])return true;
	
		if (target < arr[i][j])--i;//target小于array[i][j],上移
		else ++j;//否则右移
	}
	return false;
}
//     思路二：从左上角开始查找，先在第一行找到大于target的数，
//             然后，target比array[i][j]大时，下移；否则左移
bool Find2(vector < vector<int> > arr, int target)
{
	int rowcount = arr.size();
	int colcount = arr[0].size();

	int i = 0, j = 0;
	while (j < colcount - 1 && arr[i][j] <= target)++j;//第一行，从左往右，找到第一个大于target的数

	while (i < rowcount && j >= 0)
	{
		if (arr[i][j] == target)return true;
		
		if (arr[i][j] < target)//array[i][j]小于target，下移
			++i;
		else --j;//否则左移
	}
	return false;
}
int main()
{
	vector<vector<int> > _v(5);
	int arr[20] = {1,5,9,13,2,7,10,14,3,8,13,16,5,10,14,17,19,23,26,29};
	int i,j,index = 0;
	for(i = 0;i < 5;++i)
	{
		for(j = 0; j < 4 ;++j)
		{
			_v[i].push_back( arr[index++]);
		}
	}
	cout << Find(_v, 26) << endl;
	cout << Find2(_v, 26) << endl;

	return 0;
}
